/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: QR1 二分查找
 * <a href="https://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?tpId=182&tqId=34705&rp=1&ru=/exam/company&qru=/exam/company&sourceUrl=%2Fexam%2Fcompany&difficulty=3&judgeStatus=undefined&tags=&title=">...</a>
 * User: DELL
 * Date: 2023-10-27
 * Time: 22:44
 */
public class BinarySearch {
    /**
     * 解题思路: (二分)
     * 本题因为数组是有序的,所以上来第一思路就是二分查找,其实较为简单,
     * 本题唯一难点就是如何处理重复的元素,同时要返回重复元素最左边的
     * 那个元素的下标,这里我想到了两种解决办法,
     * 方法一: 利用二分找到元素下标后,然后依次往左边遍历,找到最左边元素即可
     * 方法二: 利用二分找到元素下标后,如果元素左边元素值与其相等,则将right
     * 改为 mid-1,然后继续进行二分.
     * 对于以上两种方法我更推荐方法二,因为方法一在元素重复很多的时候,就会
     * 退化成时间复杂度为 O(N),而方法二的时间复杂度很稳定,无论何时都是O(logN)
     * 以下解法就是方法二的解法.
     *
     * @return
     */
    public int getPos(int[] A, int n, int val) {
        int left = 0;
        int right = n - 1;
        int mid = (left + right) / 2;
        while (left < right) {
            if (A[mid] > val) {
                right = mid - 1;
            } else if (A[mid] < val) {
                left = mid + 1;
            } else {
                if (mid > 0 && A[mid - 1] == A[mid]) {
                    right = mid - 1;
                } else {
                    break;
                }
            }
            mid = (left + right) / 2;
        }
        return mid;
    }
}